package solution._0040._0040;

import common.Utils;
import netscape.security.UserTarget;

import java.util.*;

/**
 * Created by chen_snow
 * Date: 2021/5/28 20:52
 * Description: 组合总和 II
 */
public class Solution {

    public static void main(String[] args) {
        combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8);
    }

    public static HashMap<Integer, Integer> numTimeMap = new HashMap<>();
    public static ArrayList<List<Integer>> result = new ArrayList<>();

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        Utils.print(candidates);
        for (int num : candidates) {
            numTimeMap.compute(num, (key, value) -> (value == null ? 1 : value + 1));
        }
        combination(candidates, 0, target, new ArrayDeque<Integer>(), result);
        return result;
    }

    public static void combination(int[] candidates, int start, int left, Deque<Integer> dataDeque, List<List<Integer>> result) {
        if (left < 0) {
            return;
        } else if (left == 0) {
            result.add(new ArrayList<>(dataDeque));
            return;
        }

        for (int index = start; index < candidates.length; index++) {
            int numTime = numTimeMap.get(candidates[index]);
            for (int time = 1; time <= numTime; time++) {
                addLast(dataDeque, candidates[index], time);
                combination(candidates, index + numTime, calculateLeft(left, candidates[index], time), dataDeque, result);
                removeLast(dataDeque, time);
            }
            index += numTime - 1;
        }
    }

    public static void addLast(Deque<Integer> dataDeque, Integer num, Integer time) {
        for (int i = 0; i < time; i++) {
            dataDeque.addLast(num);
        }
    }

    public static void removeLast(Deque<Integer> dataDeque, Integer time) {
        for (int i = 0; i < time; i++) {
            dataDeque.removeLast();
        }
    }

    public static int calculateLeft(int all, int num, int time) {
        int left = all;
        for (int i = 0; i < time; i++) {
            left -= num;
        }
        return left;
    }
}
